{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Intervals Into Minimum Number of Groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #prefix-sum #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #前缀和 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将区间分为最少组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>intervals</code>&nbsp;，其中&nbsp;<code>intervals[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;表示 <strong>闭</strong>&nbsp;区间&nbsp;<code>[left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要将&nbsp;<code>intervals</code> 划分为一个或者多个区间&nbsp;<strong>组</strong>&nbsp;，每个区间 <b>只</b>&nbsp;属于一个组，且同一个组中任意两个区间 <strong>不相交</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <strong>最少</strong>&nbsp;需要划分成多少个组。</p>\n",
    "\n",
    "<p>如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 <strong>相交</strong>&nbsp;的。比方说区间&nbsp;<code>[1, 5]</code> 和&nbsp;<code>[5, 8]</code>&nbsp;相交。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>我们可以将区间划分为如下的区间组：\n",
    "- 第 1 组：[1, 5] ，[6, 8] 。\n",
    "- 第 2 组：[2, 3] ，[5, 10] 。\n",
    "- 第 3 组：[1, 10] 。\n",
    "可以证明无法将区间划分为少于 3 个组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>intervals = [[1,3],[5,6],[8,10],[11,13]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>所有区间互不相交，所以我们可以把它们全部放在一个组内。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-intervals-into-minimum-number-of-groups](https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-intervals-into-minimum-number-of-groups](https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,10],[6,8],[1,5],[2,3],[1,10]]', '[[1,3],[5,6],[8,10],[11,13]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        h = []\n",
    "        for left, right in intervals:\n",
    "            if h and left > h[0]:\n",
    "                heapreplace(h, right)\n",
    "            else:\n",
    "                heappush(h, right)\n",
    "        return len(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[-1])\n",
    "        sl = SortedList([0])\n",
    "        for x, y in intervals:\n",
    "            lo, hi = 0, len(sl) - 1\n",
    "            while lo < hi:\n",
    "                mid = (lo + hi + 1) // 2\n",
    "                if sl[mid] < x:\n",
    "                    lo = mid\n",
    "                else:\n",
    "                    hi = mid - 1\n",
    "            if sl[lo] < x:\n",
    "                sl.discard(sl[lo])\n",
    "            sl.add(y)\n",
    "        return len(sl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x : (x[0], x[1]))\n",
    "        n = len(intervals)\n",
    "        print(intervals)\n",
    "        # groups = [[] for i in range(n)]\n",
    "        idle = [i for i in range(n)]\n",
    "        heapq.heapify(idle)\n",
    "        using = []\n",
    "        \n",
    "        for (left, right) in intervals:\n",
    "            # print(left, right, using)\n",
    "            if len(using) != 0:\n",
    "                v, i = using[0]\n",
    "                if v < left:\n",
    "                    s = heapq.heappop(using)\n",
    "                    heapq.heappush(using, (right, s[1]))\n",
    "                    continue\n",
    "            i = heapq.heappop(idle)\n",
    "            heapq.heappush(using, (right, i))\n",
    "            \n",
    "        print('last:', using)\n",
    "        return len(using)\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0],x[1]))\n",
    "        q = []\n",
    "        for left,right in intervals:\n",
    "            if q and left > q[0]:\n",
    "                heapq.heappop(q)\n",
    "                heapq.heappush(q,right)\n",
    "            else:\n",
    "                heapq.heappush(q,right)\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        end = max([right for _, right in intervals])\n",
    "\n",
    "        diff = [0] * (end + 2)\n",
    "\n",
    "        for left, right in intervals:\n",
    "            diff[left] += 1\n",
    "            diff[right + 1] -= 1\n",
    "\n",
    "        return max(accumulate(diff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # 排序\n",
    "        intervals.sort(key=lambda x: [x[0], x[1]])\n",
    "\n",
    "        # 小根堆\n",
    "        ans = [0]\n",
    "\n",
    "        for i, j in intervals:\n",
    "            if ans[0] < i:\n",
    "                heapq.heapreplace(ans, j)\n",
    "            else:\n",
    "                heapq.heappush(ans, j)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        a=intervals\n",
    "        b=[]\n",
    "        for i,j in a:\n",
    "            b.append((i,-1))\n",
    "            b.append((j,1))\n",
    "        b.sort()\n",
    "        ans=0\n",
    "        now=0\n",
    "        for i,v in b:\n",
    "            now-=v\n",
    "            ans=max(ans,now)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        s = SortedList()\n",
    "        res = 0\n",
    "        for x, y in intervals:\n",
    "            s.add([x, y])\n",
    "        for x, y in intervals:\n",
    "            if [x, y] not in s:\n",
    "                continue\n",
    "            s.remove([x, y])\n",
    "            idx = s.bisect_left([y + 1, y + 1])\n",
    "            while s and idx < len(s):\n",
    "                idx = s.bisect_left([y + 1, y + 1])\n",
    "                if idx == len(s):continue\n",
    "                y = s[idx][-1]\n",
    "                s.remove(s[idx])\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], [1]))\n",
    "        heap = []\n",
    "        heapq.heappush(heap, intervals[0][1])\n",
    "        res = 1\n",
    "        for i in intervals[1:]:\n",
    "            if heap[0] < i[0]:\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                res += 1\n",
    "\n",
    "            heapq.heappush(heap, i[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        rr = [0]\n",
    "        for i in intervals:\n",
    "            # rr.sort()\n",
    "            if rr[0] >= i[0]:\n",
    "                heapq.heappush(rr, i[1])\n",
    "                # rr.append(i[1])\n",
    "                continue\n",
    "            # rr[0] = i[1]\n",
    "            heapq.heapreplace(rr, i[1])\n",
    "            # for r in range(len(rr)):\n",
    "            #     if rr[r] < i[0]:\n",
    "            #         rr[r] = i[1]\n",
    "            #         break\n",
    "        return len(rr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: list) -> int:\n",
    "        add = {}\n",
    "        leave = {}\n",
    "        for i in intervals:\n",
    "            if i[0] not in add.keys():\n",
    "                add[i[0]] = 1\n",
    "            else:\n",
    "                add[i[0]] += 1\n",
    "            if i[1]+1 not in leave.keys():\n",
    "                leave[i[1]+1] = 1\n",
    "            else:\n",
    "                leave[i[1]+1] += 1\n",
    "        start = min(add)\n",
    "        stop = max(leave)\n",
    "        n = 0\n",
    "        ans = 0\n",
    "        for i in range(start, stop):\n",
    "            if i not in add.keys() and i not in leave.keys():\n",
    "                continue\n",
    "            if i in add:\n",
    "                n += add[i]\n",
    "            if i in leave:\n",
    "                n -= leave[i]\n",
    "            ans = max(ans, n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        计数数组 = [0]*1000002\n",
    "        最少组数 = 0\n",
    "        for i,j in intervals:\n",
    "            计数数组[i] += 1\n",
    "            计数数组[j+1] -= 1\n",
    "        计数 = 0\n",
    "        for i in 计数数组:\n",
    "            计数 += i\n",
    "            最少组数 = max(最少组数, 计数)\n",
    "        return 最少组数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # intervals.sort(key = lambda x:x[0])\n",
    "        # n = len(intervals)\n",
    "        # mm = [[] for _ in range(n)]\n",
    "        # ans = 0\n",
    "        # for inter in intervals:\n",
    "        #     i = 0\n",
    "        #     while mm[i] and mm[i][-1][1]>inter[0]:\n",
    "        #         i+=1\n",
    "        #     mm[i].append(inter)\n",
    "        #     ans = max(ans,i)\n",
    "        #     # print(mm)\n",
    "        # return ans+1\n",
    "        m1 = [0]*(10**6+1)\n",
    "        m2 = [0]*(10**6+1)\n",
    "        for b,e in intervals:\n",
    "            m1[b] += 1\n",
    "            m2[e] -= 1\n",
    "        n = len(m1)\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur += m1[i]\n",
    "            ans = max(ans,cur)\n",
    "            cur += m2[i]\n",
    "        # print(m1[:20],m2[:20])\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        d = [0] * 1000002\n",
    "        for a, b in intervals:\n",
    "            d[a] += 1\n",
    "            d[b + 1] -= 1\n",
    "        p = ans = 0\n",
    "        for x in d:\n",
    "            p += x\n",
    "            ans = max(ans, p)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        n = 1_000_010\n",
    "        diff = [0] * n\n",
    "\n",
    "        for left, right in intervals:\n",
    "            diff[left] += 1\n",
    "            diff[right + 1] -= 1\n",
    "\n",
    "        res, pre = diff[0], diff[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if pre + diff[i] > res:\n",
    "                res = pre + diff[i]\n",
    "\n",
    "            pre += diff[i] \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        max_ = max(intervals,key=lambda x: x[1])\n",
    "        max_ = max_[1]\n",
    "        diff = [0 for i in range(max_ + 2)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            diff[intervals[i][0]] += 1\n",
    "            diff[intervals[i][1] + 1] -= 1\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        for i in range(1,max_+1):\n",
    "            total += diff[i]\n",
    "            ans = max(total, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        max1=0\n",
    "        for interval in intervals:\n",
    "            max1=max(interval[-1],max1)\n",
    "        ls=[0 for i in range(max1+2)]\n",
    "        for interval in intervals:\n",
    "            ls[interval[0]] += 1\n",
    "            ls[interval[1] + 1] += -1\n",
    "        rmax=0\n",
    "        sum=0\n",
    "        for i in ls:\n",
    "            sum+=i\n",
    "            rmax=max(rmax,sum)\n",
    "        return rmax\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        events = []\n",
    "        for s, e in intervals:\n",
    "            events.append([s, 1])\n",
    "            events.append([e + 1, - 1])\n",
    "        events.sort()\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for t, val in events:\n",
    "            cur += val\n",
    "            res = max(res, cur)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        points = []\n",
    "        for interval in intervals:\n",
    "            if interval[0] == interval[1]:\n",
    "                points.append([interval[0],3])\n",
    "            points.append([interval[0], 1])\n",
    "            points.append([interval[1], 2])\n",
    "        points.sort()\n",
    "        max_ = 0\n",
    "        cnt = 0\n",
    "        cov_point = 0\n",
    "        for point in points:\n",
    "            if point[1] == 1:cov_point += point[1]\n",
    "            if cov_point > max_:\n",
    "                max_ = cov_point\n",
    "                cnt += 1\n",
    "            elif cov_point == max_:\n",
    "                cnt += 1\n",
    "            if point[1] == 2 or point[1] == 3:cov_point -= 1\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        for a,b in intervals:\n",
    "            A.append([a,1])\n",
    "            A.append([b+1,-1])\n",
    "        res = cur = 0\n",
    "        for _,diff in sorted(A):\n",
    "            cur+=diff\n",
    "            res=max(res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for start, end in intervals:\n",
    "            diff[start] += 1\n",
    "            diff[end + 1] -= 1\n",
    "        nums = [diff[key] for key in sorted(diff)]\n",
    "        return max(accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff_map = collections.defaultdict(int)\n",
    "        for left, right in intervals:\n",
    "            diff_map[left] += 1\n",
    "            diff_map[right+1] -= 1\n",
    "        \n",
    "        ans = 0\n",
    "        accu = 0\n",
    "        for pos in sorted(diff_map):\n",
    "            accu += diff_map[pos]\n",
    "            if accu > ans:\n",
    "                ans = accu \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # intervals.sort()\n",
    "        # stack = [-1]\n",
    "        # for i,j in intervals:\n",
    "        #     if stack[0] < i:\n",
    "        #         heappop(stack)\n",
    "        #     heappush(stack,j)\n",
    "        # return len(stack)\n",
    "        record = defaultdict(lambda : 0)\n",
    "        for i,j in intervals:\n",
    "            record[i] += 1\n",
    "            record[j+1] -= 1\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for k in sorted(record):\n",
    "            cur += record[k]\n",
    "            ans = max(cur,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        d = SortedDict()\n",
    "        for start, end in intervals:\n",
    "            d[start] = d.setdefault(start, 0) + 1\n",
    "            d[end + 1] = d.setdefault(end + 1, 0) - 1\n",
    "        ans = maxBook = 0\n",
    "        for freq in d.values():\n",
    "            maxBook += freq\n",
    "            ans = max(ans, maxBook)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        # 按左端点对intervals数组升序排序\n",
    "        intervals.sort(key=lambda p: p[0])\n",
    "\n",
    "        # 最小堆：储存新组的区间右端点，元素：(右端点值, 组号)\n",
    "        h = []\n",
    "\n",
    "        # 哈希表，储存区间组，key: 组的编号，value: 区间组成的列表\n",
    "        hashmap = defaultdict(list)\n",
    "\n",
    "        # 最大组号\n",
    "        max_group_id = 1\n",
    "\n",
    "        # 从前往后遍历每个区间\n",
    "        for interval in intervals:\n",
    "            L, R = interval\n",
    "\n",
    "            if h:\n",
    "                right, group_id = h[0]\n",
    "                max_group_id = max(max_group_id, group_id)\n",
    "                # 若该区间左端点大于最小的右端点，则能接在它后面\n",
    "                if L > right:\n",
    "                    heapreplace(h, (R, group_id))\n",
    "                    hashmap[group_id].append(interval)\n",
    "                # 若不能，新开一个组\n",
    "                else: \n",
    "                    max_group_id += 1\n",
    "                    heappush(h, (R, max_group_id))\n",
    "\n",
    "                    hashmap[max_group_id].append(interval)\n",
    "            else:\n",
    "                heappush(h, (R, max_group_id))\n",
    "                hashmap[max_group_id].append(interval)\n",
    "\n",
    "        # print(hashmap)\n",
    "        return max_group_id\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        ans = []\n",
    "        d = defaultdict(int)\n",
    "        # 标记区间内的每个数字之后的数字出现了多少次\n",
    "        for x, y in intervals:\n",
    "            d[x] += 1\n",
    "            d[y + 1] -= 1\n",
    "        ans = accumulate(d[i] for i in sorted(d))\n",
    "        return max(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        d = collections.defaultdict(lambda:0)\n",
    "        for left, right in intervals:\n",
    "            d[left] += 1\n",
    "            d[right + 1] -= 1\n",
    "        ans = 0\n",
    "        c = 0\n",
    "        for k in sorted(list(d.keys())):\n",
    "            c += d[k]\n",
    "            print(c)\n",
    "            ans = max(ans, c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff=defaultdict(int)\n",
    "        for i,j in intervals:\n",
    "            diff[i]+=1\n",
    "            diff[j+1]-=1\n",
    "        res=s=0\n",
    "        for k in sorted(diff):\n",
    "            s+=diff[k]\n",
    "            res=max(res,s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        import collections\n",
    "        arr = collections.defaultdict(int)\n",
    "        for start, end in intervals:\n",
    "            arr[start] += 1\n",
    "            arr[end+1] -= 1\n",
    "        result = 0\n",
    "        tmp = 0\n",
    "        for i in sorted(arr.keys()):\n",
    "            tmp += arr[i]\n",
    "            if tmp > result:\n",
    "                result = tmp\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        a = []\n",
    "        for each in intervals:\n",
    "            a.append((each[0], 1))\n",
    "            a.append((each[1], -1))\n",
    "        def cmp(a, b):\n",
    "            if a[0] == b[0]:\n",
    "                return b[1] - a[1]\n",
    "            else:\n",
    "                return a[0] - b[0]\n",
    "        a.sort(key = cmp_to_key(cmp))\n",
    "        cnt = 0\n",
    "        maxm = 0\n",
    "        for each in a:\n",
    "            cnt += each[1]\n",
    "            maxm = max(maxm, cnt)\n",
    "        # print(a)\n",
    "        return maxm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: list) -> int:\n",
    "        add = {}\n",
    "        leave = {}\n",
    "        allpoints = set([])\n",
    "        for i in intervals:\n",
    "            allpoints.add(i[0])\n",
    "            allpoints.add(i[1]+1)\n",
    "            if i[0] not in add.keys():\n",
    "                add[i[0]] = 1\n",
    "            else:\n",
    "                add[i[0]] += 1\n",
    "            if i[1]+1 not in leave.keys():\n",
    "                leave[i[1]+1] = 1\n",
    "            else:\n",
    "                leave[i[1]+1] += 1\n",
    "        allpoints = sorted(list(allpoints))\n",
    "        n = 0\n",
    "        ans = 0\n",
    "        for i in allpoints:\n",
    "            if i not in add.keys() and i not in leave.keys():\n",
    "                continue\n",
    "            if i in add:\n",
    "                n += add[i]\n",
    "            if i in leave:\n",
    "                n -= leave[i]\n",
    "            ans = max(ans, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        xf = collections.defaultdict(int)\n",
    "        for l, r in intervals:\n",
    "            xf[l] += 1\n",
    "            xf[r + 1] -= 1\n",
    "\n",
    "        a = [(x, f) for x, f in xf.items()]\n",
    "        a.sort()\n",
    "\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for x, f in a:\n",
    "            cur += f\n",
    "            res = max(res, cur)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 差分\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        xf = collections.defaultdict(int)\n",
    "        for l, r in intervals:\n",
    "            xf[l] += 1\n",
    "            xf[r + 1] -= 1\n",
    "\n",
    "        a = [(x, f) for x, f in xf.items()]\n",
    "        a.sort()\n",
    "\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for x, f in a:\n",
    "            cur += f\n",
    "            res = max(res, cur)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    # heap\n",
    "    def minGroups2(self, intervals: List[List[int]]) -> int:\n",
    "        #划分最小的不相交区间\n",
    "        #[1,5],[1,10],[2,3],[5,10],[6,8]\n",
    "        sorted_intervals = sorted(intervals,key=lambda x:x[0])\n",
    "\n",
    "        print(sorted_intervals)\n",
    "\n",
    "        heap = []\n",
    "        for left,right in sorted_intervals:\n",
    "            if heap and left > heap[0]:#大于当前划分最小右边界，可以加入这个分组\n",
    "                print(left)\n",
    "                print(heap[0])\n",
    "\n",
    "                # heapreplace(heap, item) - Pop and return the smallest item from the heap, and also push the new item. \n",
    "                # heappushpop(heap, item) - Push item on the heap, then pop and return the smallest item from the heap.\n",
    "                heapreplace(heap,right)#更新堆顶，重建小顶堆\n",
    "            else:\n",
    "                heappush(heap,right)#新建分组\n",
    "\n",
    "            print(heap)\n",
    "        return len(heap)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for x, y in intervals:\n",
    "            d[x] += 1\n",
    "            d[y + 1] -= 1\n",
    "        a = sorted(d.items())\n",
    "        ans = acc = 0\n",
    "        for _, v in a:\n",
    "            acc += v\n",
    "            ans = max(ans, acc )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O()\n",
    "        # space: O()\n",
    "        \n",
    "        intervals.sort(key = lambda x: (x[0], x[1]))\n",
    "        f = {}\n",
    "        for s,e in intervals:\n",
    "            f[s] = f.get(s, 0) + 1\n",
    "            f[e+1] = f.get(e+1, 0) - 1\n",
    "        layers = 0\n",
    "        res = 0\n",
    "        for v in sorted(f.keys()):\n",
    "            layers += f[v]\n",
    "            res = max(res, layers)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals) < 2:\n",
    "            return 1\n",
    "        stack = []\n",
    "        for i in intervals:\n",
    "            stack.append((i[0],1))\n",
    "            stack.append((i[1],-1))\n",
    "        stack.sort(key = lambda x:(x[0],-x[1]))\n",
    "        #print(stack)\n",
    "        temp,cost =0,0\n",
    "        ans = 0\n",
    "        for idx,cost in stack:\n",
    "            temp += cost\n",
    "            ans = max(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        qu=[]\n",
    "        for i in intervals:\n",
    "            qu.append([i[0],1])\n",
    "            qu.append([i[1],-1])\n",
    "        def f(x,y):\n",
    "            return x[0]-y[0] if x[0]!=y[0] else y[1]-x[1]\n",
    "        qu=sorted(qu,key=functools.cmp_to_key(f))\n",
    "        s=0\n",
    "        res=1\n",
    "        for i in qu:\n",
    "            s+=i[1]\n",
    "            res=max(res,s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        lines = defaultdict(int)\n",
    "        for start,end in intervals:\n",
    "            lines[start] += 1\n",
    "            lines[end+1] -= 1\n",
    "        lines = sorted([[k,v] for k,v in lines.items()])\n",
    "        result = [lines[i][1] for i in range(len(lines))]\n",
    "        for i in range(1,len(result)):\n",
    "            result[i] += result[i-1]\n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals) < 2:\n",
    "            return 1\n",
    "        stack = []\n",
    "        for i in intervals:\n",
    "            stack.append((i[0],1))\n",
    "            stack.append((i[1],-1))\n",
    "        stack.sort(key = lambda x:(x[0],-x[1]))\n",
    "        print(stack)\n",
    "        temp,cost =0,0\n",
    "        ans = 0\n",
    "        for idx,cost in stack:\n",
    "            temp += cost\n",
    "            ans = max(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        arr = []\n",
    "        for s, e in intervals:\n",
    "            arr.append((s, 1))\n",
    "            arr.append((e, -1))\n",
    "        arr.sort(key = lambda x : [x[0], -x[1]])\n",
    "        for _, i in arr:\n",
    "            tmp += i\n",
    "            res = max(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = [[0, 0] for _ in range(len(intervals)*2)]    # 差分数组\n",
    "        for i in range(len(intervals)*2):\n",
    "            if i % 2 == 0:\n",
    "                diff[i][0] = intervals[i//2][0]\n",
    "                diff[i][1] = 1\n",
    "            else:\n",
    "                diff[i][0] = intervals[i//2][1]\n",
    "                diff[i][1] = -1\n",
    "        diff.sort(key=lambda x:(x[0], -x[1]))   # 如果两个时间点重合，让开始在前\n",
    "        cur = ans = 0\n",
    "        for d in diff:\n",
    "            if d[1] == 1:\n",
    "                cur += 1\n",
    "                ans = max(cur, ans)\n",
    "            else:\n",
    "                cur -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        s = set()\n",
    "        for l, r in intervals:\n",
    "            s.add(l)\n",
    "            s.add(r)\n",
    "\n",
    "        s = list(s)\n",
    "        s.sort()\n",
    "\n",
    "        m = {}\n",
    "        for i, p in enumerate(s):\n",
    "            m[p] = i\n",
    "\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for l, r in intervals:\n",
    "            diff[m[l]] += 1\n",
    "            diff[m[r] + 1] -=1\n",
    "\n",
    "        for i in range(len(s) ):\n",
    "            diff[i + 1] += diff[i]\n",
    "\n",
    "        return max(diff) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    m = np.zeros(10**6+2)\n",
    "    max = 0\n",
    "    # 此处应该进行一维差分，因为left和right之间的距离可能很大，通过一维差分可以避免对大范围内的数进行+1运算  \n",
    "    def insert(self, x, y):\n",
    "        self.m[x] += 1\n",
    "        self.m[y+1] -= 1\n",
    "        return 0\n",
    "    \n",
    "    def prefix_sum(self, length):\n",
    "        for i in range(1, length+1):\n",
    "            self.m[i] += self.m[i-1]\n",
    "\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        self.m = np.zeros(10**6+2)\n",
    "        self.max = 0\n",
    "        for i in range(0, len(intervals)):\n",
    "            x, y = intervals[i]\n",
    "            if y > self.max:\n",
    "                self.max = y\n",
    "            self.insert(x, y)\n",
    "        self.prefix_sum(self.max+1)\n",
    "        t = int(max(self.m))\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        xf = collections.defaultdict(int)\n",
    "        for l, r in intervals:\n",
    "            xf[l] += 1\n",
    "            xf[r + 1] -= 1\n",
    "\n",
    "        a = [(x, f) for x, f in xf.items()]\n",
    "        a.sort()\n",
    "\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for x, f in a:\n",
    "            cur += f\n",
    "            res = max(res, cur)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        xf = collections.defaultdict(int)\n",
    "        for l, r in intervals:\n",
    "            xf[l] += 1\n",
    "            xf[r + 1] -= 1\n",
    "\n",
    "        a = [(x, f) for x, f in xf.items()]\n",
    "        a.sort()\n",
    "\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for x, f in a:\n",
    "            cur += f\n",
    "            res = max(res, cur)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "\n",
    "        for x,y in intervals:\n",
    "            diff[x] += 1\n",
    "            diff[y+1] -= 1\n",
    "\n",
    "        d = sorted(diff.items())\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for k,v in d:\n",
    "            s += v\n",
    "            ans = max(ans,s)\n",
    "        return ans\n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        vals = set()\n",
    "        for s,e in intervals:\n",
    "            vals.add(s)\n",
    "            vals.add(e + 1)\n",
    "        rm = {}\n",
    "        for ind, val in enumerate(sorted(vals)):\n",
    "            rm[val] = ind + 1\n",
    "        \n",
    "        d = [0] *(len(vals) + 1)\n",
    "\n",
    "        for s,e in intervals:\n",
    "            i,j = rm[s], rm[e + 1]\n",
    "            d[i] += 1\n",
    "            d[j] -= 1\n",
    "        s = 0\n",
    "        res = 0\n",
    "        for i in range(len(d)):\n",
    "            s += d[i]\n",
    "            if s > res: res = s\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x:-x[1])\n",
    "        n = intervals[0][1] + 1\n",
    "        data = [0] * (n + 1)\n",
    "        for start, end in intervals:\n",
    "            data[start] += 1\n",
    "            # print(end, n)\n",
    "            data[end + 1] -= 1\n",
    "        \n",
    "        # print(data)\n",
    "        for i in range(1, n):\n",
    "            data[i] = data[i-1] + data[i]\n",
    "        \n",
    "        \n",
    "        return max(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        N = 10**6 + 2\n",
    "        arr = [0] * N\n",
    "        for i, j in intervals:\n",
    "            arr[i] += 1\n",
    "            arr[j + 1] -= 1\n",
    "        for i in range(1, N):\n",
    "            arr[i] += arr[i - 1]\n",
    "            ret=max(ret,arr[i])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        N = 10**6+2\n",
    "        arr = [0]*N\n",
    "        for i in intervals:\n",
    "            arr[i[0]]+=1\n",
    "            arr[i[1]+1]-=1\n",
    "        for i in range(1,N):\n",
    "            arr[i]+=arr[i-1]\n",
    "            ret=max(ret,arr[i])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        res = 0\n",
    "        lenthnum = max(intervals[i][1] for i in range(len(intervals))) + 2\n",
    "        chafennums = [0] * lenthnum\n",
    "        for interval in intervals:\n",
    "            chafennums[interval[0]] += 1\n",
    "            chafennums[interval[1] + 1] -= 1\n",
    "        for i in range(1, len(chafennums)):\n",
    "            chafennums[i] += chafennums[i - 1]\n",
    "            res = max(res, chafennums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff=[0]*(max(r for _,r in intervals)+3)\n",
    "        for l,r in intervals:\n",
    "            diff[l]+=1\n",
    "            diff[r+1]-=1\n",
    "        \n",
    "        for i in range(1,len(diff)):\n",
    "            diff[i]+=diff[i-1]\n",
    "        return max(diff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = [0 for i in range(max([j[1] for j in intervals])+2)]\n",
    "        for l,r in intervals:\n",
    "            diff[l]+=1\n",
    "            diff[r+1]-=1\n",
    "        for k in range(1,len(diff)):\n",
    "            diff[k]+=diff[k-1]\n",
    "        return max(diff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # 最小分组数 = 区间重叠数最大的\n",
    "        pfxs = [0]\n",
    "        res = 0\n",
    "        for start,end in intervals:\n",
    "            while end+2 > len(pfxs): pfxs.append(0)\n",
    "            pfxs[start] += 1\n",
    "            pfxs[end+1]   -= 1\n",
    "        n = len(pfxs)\n",
    "        for i in range(1,n):\n",
    "            pfxs[i] += pfxs[i-1]\n",
    "            if pfxs[i] > res:\n",
    "                res = pfxs[i]\n",
    "        #print(pfxs)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        maxNum = max([i[-1] for i in intervals])\n",
    "        dp = [0] * (maxNum + 1)\n",
    "        for i in range(len(intervals)):\n",
    "            dp[intervals[i][0]] += 1\n",
    "            if intervals[i][1] < maxNum:\n",
    "                dp[intervals[i][1]+1] -= 1\n",
    "        ans = 0\n",
    "        for i in range(1,maxNum+1):\n",
    "            dp[i] += dp[i-1]\n",
    "            ans = max(ans,dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # 最小分组数 = 区间重叠数最大的\n",
    "        pfxs = [0]\n",
    "        res = 0\n",
    "        for start,end in intervals:\n",
    "            while end+2 > len(pfxs): pfxs.append(0)\n",
    "            pfxs[start] += 1\n",
    "            pfxs[end+1]   -= 1\n",
    "        n = len(pfxs)\n",
    "        for i in range(1,n):\n",
    "            pfxs[i] += pfxs[i-1]\n",
    "            if pfxs[i] > res:\n",
    "                res = pfxs[i]\n",
    "        #print(pfxs)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        mp = dict()\n",
    "        for a in intervals:\n",
    "            if a[0] in mp:\n",
    "                mp[a[0]] += 1\n",
    "            else:\n",
    "                mp[a[0]] = 1\n",
    "            if a[1]+1 in mp:\n",
    "                mp[a[1]+1] -= 1\n",
    "            else:\n",
    "                mp[a[1]+1] = -1\n",
    "                \n",
    "        def sortDict(data) -> dict:\n",
    "            return dict(sorted(data.items(), key=operator.itemgetter(0), reverse=False))\n",
    "        \n",
    "        mp = sortDict(mp)\n",
    "        \n",
    "        cur, ans = 0, 0\n",
    "        for a in mp.keys():\n",
    "            cur += mp[a]\n",
    "            ans = max(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        # 最小分组数 = 区间重叠数最大的\n",
    "        max_len = max(e for _,e in intervals)\n",
    "        pfxs = [0]*(max_len+2)\n",
    "        res = 0\n",
    "        for start,end in intervals:\n",
    "            pfxs[start] += 1\n",
    "            pfxs[end+1]   -= 1\n",
    "        n = len(pfxs)\n",
    "        for i in range(1,n):\n",
    "            pfxs[i] += pfxs[i-1]\n",
    "        return max(pfxs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        inputnums=len(intervals)\n",
    "\n",
    "        max_num=0\n",
    "        min_num=9999999\n",
    "        for i in range(inputnums):\n",
    "            for j in range(2):\n",
    "                if intervals[i][j]<min_num:\n",
    "                    min_num=intervals[i][j]\n",
    "                if intervals[i][j]>max_num:\n",
    "                    max_num=intervals[i][j]\n",
    "        len_diff=(max_num-min_num+1)\n",
    "        diff=[0]*len_diff\n",
    "        val=[0]*len_diff\n",
    "        for k in range(inputnums):\n",
    "            i=intervals[k][0]-min_num\n",
    "            j=intervals[k][1]-min_num\n",
    "            \n",
    "            diff[i]=diff[i]+1\n",
    "            if j+1<len_diff:\n",
    "                diff[j+1]=diff[j+1]-1\n",
    "        \n",
    "        val[0]=diff[0]\n",
    "        for k in range(1,len_diff,1):\n",
    "            #print(k)\n",
    "            val[k]=val[k-1]+diff[k]\n",
    "\n",
    "        \n",
    "        max_groups=0\n",
    "        for k in val:\n",
    "            if k>max_groups:\n",
    "                max_groups=k\n",
    "        \n",
    "\n",
    "        return max_groups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = [0]*(max(itv[1] for itv in intervals)+2) \n",
    "        for s,e in intervals:\n",
    "            diff[s]+=1\n",
    "            diff[e+1]-=1 \n",
    "        for j in range(1,len(diff)):\n",
    "            diff[j]+=diff[j-1] \n",
    "        return max(diff) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        diff = [0]*(10**6+2)\n",
    "        for l,r in intervals:\n",
    "            diff[l] += 1\n",
    "            diff[r+1] -= 1\n",
    "        ans = diff[0]\n",
    "        for i in range(1,10**6+2):\n",
    "            diff[i] += diff[i-1]\n",
    "            ans = max(ans,diff[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x:x[1])\n",
    "        maxl = intervals[-1][-1] #\n",
    "        diff = [0]*(maxl)\n",
    "        for x,y in intervals:\n",
    "            diff[x-1] += 1 \n",
    "            if  y <maxl:\n",
    "                diff[y]-= 1\n",
    "        ans = diff[0]\n",
    "        for i in range(1,maxl):\n",
    "            diff[i] = diff[i-1] +diff[i]\n",
    "            ans = max(ans,diff[i])\n",
    "        return ans\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        n = max([i for _,i in intervals])\n",
    "\n",
    "        s = [0] * (n+2)\n",
    "\n",
    "        for i,j in intervals:\n",
    "            s[i] += 1\n",
    "            s[j+1] -= 1\n",
    "\n",
    "        return max([i for i in accumulate(s)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroups(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        res = [0] * (10 ** 6 + 2)\n",
    "        l,r = 0,0\n",
    "        intervals = sorted(intervals)\n",
    "        for l,r in intervals:\n",
    "            res[l] += 1\n",
    "            res[r+1] -= 1\n",
    "        ans = [s for s in accumulate(res)]\n",
    "        return max(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
